class SudokuGenerator {
    constructor() {
        this.SIZE = 9;
        this.BOX_SIZE = 3;
        this.DIFFICULTY_SETTINGS = {
            easy: { minClues: 36, maxClues: 45, maxAttempts: 100 },
            medium: { minClues: 28, maxClues: 35, maxAttempts: 500 },
            hard: { minClues: 22, maxClues: 27, maxAttempts: 1000 },
            expert: { minClues: 17, maxClues: 21, maxAttempts: 2000 }
        };
    }

    /**
     * 生成数独题目和答案
     * 先创建出一个完整的数独解，然后根据难度设置移除数字，确保谜题有唯一解。
     * @param {string} difficulty - 难度级别: 'easy', 'medium', 'hard', 'expert'
     * @returns {Object} { puzzle: number[][], solution: number[][], difficulty: string }
     */
    generateSudoku(difficulty = 'medium') {
        const settings = this.DIFFICULTY_SETTINGS[difficulty];
        if (!settings) {
            throw new Error('无效的难度级别，请选择: easy, medium, hard, expert');
        }

        let puzzle, solution;
        let attempts = 0;

        do {
            // 生成完整解
            solution = this.generateFullSudoku();

            // 创建谜题
            // 修正这里的深拷贝方式
            puzzle = this.removeNumbers(solution.map(row => [...row]), settings);

            attempts++;

            if (attempts > settings.maxAttempts * 2) {
                throw new Error('生成题目失败，请重试');
            }

        } while (!this.hasUniqueSolution(puzzle));

        return {
            puzzle: puzzle,
            solution: solution,
            difficulty: difficulty,
            clues: this.countClues(puzzle)
        };
    }

    /**
     * 生成完整的数独解
     */
    generateFullSudoku() {
        const board = Array(9).fill().map(() => Array(9).fill(0));
        this.solveSudoku(board, true);
        return board;
    }

    /**
     * 移除数字创建谜题
     */
    removeNumbers(board, settings) {
        const cells = [];
        
        // 生成所有单元格位置
        for (let i = 0; i < this.SIZE; i++) {
            for (let j = 0; j < this.SIZE; j++) {
                cells.push([i, j]);
            }
        }
        
        // 随机打乱单元格顺序
        this.shuffleArray(cells);
        
        // 计算要保留的数字数量
        const cluesToKeep = settings.minClues + 
            Math.floor(Math.random() * (settings.maxClues - settings.minClues + 1));
        
        const cellsToRemove = this.SIZE * this.SIZE - cluesToKeep;
        
        // 移除数字
        let removed = 0;
        for (let i = 0; i < cells.length && removed < cellsToRemove; i++) {
            const [row, col] = cells[i];
            const temp = board[row][col];
            
            if (temp !== 0) {
                board[row][col] = 0;
                
                // 检查是否仍然有唯一解
                if (this.hasUniqueSolution(board)) {
                    removed++;
                } else {
                    // 如果没有唯一解，恢复数字
                    board[row][col] = temp;
                }
            }
        }
        
        return board;
    }

    /**
     * 检查是否有唯一解
     */
    hasUniqueSolution(board) {
        const solutions = [];
        // 直接传递二维数组
        this.countSolutions(board.map(row => [...row]), solutions);
        return solutions.length === 1;
    }

    /**
     * 计算解的数量
     */
    countSolutions(board, solutions, maxSolutions = 2) {
        if (solutions.length >= maxSolutions) return;

        for (let row = 0; row < this.SIZE; row++) {
            for (let col = 0; col < this.SIZE; col++) {
                if (board[row][col] === 0) {
                    // 尝试所有可能的数字
                    for (let num = 1; num <= 9; num++) {
                        if (this.isValidMove(board, row, col, num)) {
                            board[row][col] = num;
                            this.countSolutions(board, solutions, maxSolutions);
                            if (solutions.length >= maxSolutions) return;
                            // 回溯
                            board[row][col] = 0;
                        }
                    }
                    return;
                }
            }
        }
        // 这里只需要二维数组
        solutions.push(board.map(row => [...row]));
    }

    /**
     * 解数独（用于生成完整解）
     */
    solveSudoku(board, generate = false) {
        for (let row = 0; row < this.SIZE; row++) {
            for (let col = 0; col < this.SIZE; col++) {
                if (board[row][col] === 0) {
                    //shuffleArray 随机打乱数组元素的顺序
                    let numbers = generate ? this.shuffleArray([1, 2, 3, 4, 5, 6, 7, 8, 9]) : [1, 2, 3, 4, 5, 6, 7, 8, 9];
                    
                    for (let num of numbers) {
                        if (this.isValidMove(board, row, col, num)) {
                            board[row][col] = num;
                            
                            if (this.solveSudoku(board, generate)) {
                                return true;
                            }
                            
                            // 回溯
                            board[row][col] = 0;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 检查移动是否有效
     */
    isValidMove(board, row, col, num) {
        // 检查行
        for (let x = 0; x < this.SIZE; x++) {
            if (board[row][x] === num) return false;
        }
        
        // 检查列
        for (let x = 0; x < this.SIZE; x++) {
            if (board[x][col] === num) return false;
        }
        
        // 检查3x3宫格
        const startRow = row - row % this.BOX_SIZE;
        const startCol = col - col % this.BOX_SIZE;
        
        for (let i = 0; i < this.BOX_SIZE; i++) {
            for (let j = 0; j < this.BOX_SIZE; j++) {
                if (board[i + startRow][j + startCol] === num) return false;
            }
        }
        
        return true;
    }

    /**
     * 打乱数组
     */
    shuffleArray(array) {
        for (let i = array.length - 1; i > 0; i--) {
            const j = Math.floor(Math.random() * (i + 1));
            [array[i], array[j]] = [array[j], array[i]];
        }
        return array;
    }

    /**
     * 计算提示数字数量
     */
    countClues(board) {
        return board.flat().filter(cell => cell !== 0).length;
    }

    /**
     * 打印数独棋盘
     */
    printBoard(board, title = '') {
        console.log(title);
        console.log('┌───────┬───────┬───────┐');
        
        for (let i = 0; i < this.SIZE; i++) {
            let row = '│ ';
            for (let j = 0; j < this.SIZE; j++) {
                row += (board[i][j] === 0 ? '·' : board[i][j]) + ' ';
                if ((j + 1) % 3 === 0) row += '│ ';
            }
            console.log(row);
            
            if ((i + 1) % 3 === 0 && i !== 8) {
                console.log('├───────┼───────┼───────┤');
            }
        }
        
        console.log('└───────┴───────┴───────┘');
    }

    /**
     * 验证数独解是否正确
     */
    validateSolution(puzzle, solution) {
        // 检查所有原始数字是否匹配
        for (let i = 0; i < this.SIZE; i++) {
            for (let j = 0; j < this.SIZE; j++) {
                if (puzzle[i][j] !== 0 && puzzle[i][j] !== solution[i][j]) {
                    return false;
                }
            }
        }
        
        // 检查解是否有效
        return this.isValidBoard(solution);
    }

    /**
     * 检查完整数独是否有效
     */
    isValidBoard(board) {
        // 检查行
        for (let i = 0; i < this.SIZE; i++) {
            const rowSet = new Set();
            for (let j = 0; j < this.SIZE; j++) {
                if (board[i][j] === 0 || rowSet.has(board[i][j])) return false;
                rowSet.add(board[i][j]);
            }
        }
        
        // 检查列
        for (let j = 0; j < this.SIZE; j++) {
            const colSet = new Set();
            for (let i = 0; i < this.SIZE; i++) {
                if (board[i][j] === 0 || colSet.has(board[i][j])) return false;
                colSet.add(board[i][j]);
            }
        }
        
        // 检查3x3宫格
        for (let boxRow = 0; boxRow < this.SIZE; boxRow += this.BOX_SIZE) {
            for (let boxCol = 0; boxCol < this.SIZE; boxCol += this.BOX_SIZE) {
                const boxSet = new Set();
                for (let i = 0; i < this.BOX_SIZE; i++) {
                    for (let j = 0; j < this.BOX_SIZE; j++) {
                        const num = board[boxRow + i][boxCol + j];
                        if (num === 0 || boxSet.has(num)) return false;
                        boxSet.add(num);
                    }
                }
            }
        }
        
        return true;
   }

    /**
     * 批量生成数独题目
     * @param {string} difficulty - 难度级别: 'easy', 'medium', 'hard', 'expert'
     * @param {number} count - 生成题目数量
     * @returns {Array} 题目数组，每项包含 puzzle, solution, difficulty, clues
     */
    generate(difficulty = 'medium', count = 10) {
        const result = [];
        const puzzleSet = new Set();
        let generated = 0;
        let attempts = 0;
        const maxAttempts = count * 10;

        while (generated < count && attempts < maxAttempts) {
            try {
                const info = this.generateSudoku(difficulty);
                const puzzleStr = JSON.stringify(info.puzzle);
                // 用 Set 判断是否重复
                if (!puzzleSet.has(puzzleStr)) {
                    result.push(info);
                    puzzleSet.add(puzzleStr);
                    generated++;
                }
            } catch (err) {
                // 跳过失败
            }
            attempts++;
        }
        return result;
    }
}

// 使用示例
function main() {
    const generator = new SudokuGenerator();
    
    console.log('=== 数独题目生成器 ===\n');
    
    // 生成不同难度的题目
    const difficulties = ['easy', 'medium', 'hard', 'expert'];
    
    for (const difficulty of difficulties) {
        console.log(`\n--- ${difficulty.toUpperCase()} 难度 ---`);
        
        try {
            const { puzzle, solution, clues } = generator.generateSudoku(difficulty);
            
            generator.printBoard(puzzle, `题目 (${clues} 个提示数字):`);
            generator.printBoard(solution, '答案:');
            
            // 验证解
            const isValid = generator.validateSolution(puzzle, solution);
            console.log(`验证结果: ${isValid ? '✓ 正确' : '✗ 错误'}`);
            
        } catch (error) {
            console.log(`生成失败: ${error.message}`);
        }
    }
}

// 导出模块
if (require.main === module) {
    //main();
    //测试生成100个简单题目
    const generator = new SudokuGenerator();
    const puzzles = generator.generate('easy', 100);
    console.log(`生成了 ${puzzles.length} 个简单难度的数独题目。`);
    //循环打印每个题目的提示数字数量
    puzzles.forEach((p, index) => {
        console.log(`题目 ${index + 1}: 提示数字 ${p.clues} 个`);
        generator.printBoard(p.puzzle, `题目 ${index + 1} (${p.clues} 个提示数字):`);
        generator.printBoard(p.solution, `答案 ${index + 1}:`);
    });
} else {
    module.exports = SudokuGenerator;
}

//运行：node backend/src/utils/sudoku-generator.js